//
// Created by yangchao on 2022/5/15.
// 91. 解码方法: https://leetcode.cn/problems/decode-ways/
//

#include <string>
#include <vector>
#include <iostream>
using namespace std;

//动态规划
class NumDecodings{
public:
    int numDecodings(string s) {
        int len = s.size();
        s = " "+s;
        vector<int> dp(len+1,0);
        dp[0] = 1;
        for (int i = 1; i <= len; ++i ) {
            int va = s[i] - '0';
            int vb = (s[i-1] - '0')*10 +s[i] -'0';
            if (va >= 1 && va <= 9) dp[i] = dp[i-1];
            if (vb >= 10 && vb <= 26)dp[i] += dp[i-2];
        }
        return dp[len];
    }
};

int main() {
    NumDecodings nd;
    int res = nd.numDecodings("226");
    cout << res << endl;
}